package nachos.threads;

import nachos.machine.*;

import java.util.LinkedList;
import java.util.TreeSet;
import java.util.HashSet;
import java.util.Iterator;
import java.util.PriorityQueue;



/**
 * A scheduler that chooses threads based on their priorities.
 * 
 * <p>
 * A priority scheduler associates a priority with each thread. The next thread
 * to be dequeued is always a thread with priority no less than any other
 * waiting thread's priority. Like a round-robin scheduler, the thread that is
 * dequeued is, among all the threads of the same (highest) priority, the thread
 * that has been waiting longest.
 * 
 * <p>
 * Essentially, a priority scheduler gives access in a round-robin fassion to
 * all the highest-priority threads, and ignores all other threads. This has the
 * potential to starve a thread if there's always a thread waiting with higher
 * priority.
 * 
 * <p>
 * A priority scheduler must partially solve the priority inversion problem; in
 * particular, priority must be donated through locks, and through joins.
 */
public class LotteryScheduler extends Scheduler {
	/**
	 * Allocate a new priority scheduler.
	 */
	public LotteryScheduler() {
	}

	/**
	 * Allocate a new priority thread queue.
	 * 
	 * @param transferPriority <tt>true</tt> if this queue should transfer
	 * priority from waiting threads to the owning thread.
	 * @return a new priority thread queue.
	 */
	public ThreadQueue newThreadQueue(boolean transferPriority) {
		return new PriorityThreadQueue(transferPriority);
	}

	public int getPriority(KThread thread) {
		Lib.assertTrue(Machine.interrupt().disabled());

		return getThreadState(thread).getPriority();
	}

	public int getEffectivePriority(KThread thread) {
		Lib.assertTrue(Machine.interrupt().disabled());

		return getThreadState(thread).getEffectivePriority();
	}

	public void setPriority(KThread thread, int priority) {
		Lib.assertTrue(Machine.interrupt().disabled());

		Lib.assertTrue(priority >= priorityMinimum &&
				priority <= priorityMaximum);

		getThreadState(thread).setPriority(priority);
	}

	public boolean increasePriority() {
		boolean intStatus = Machine.interrupt().disable();

		KThread thread = KThread.currentThread();

		int priority = getPriority(thread);
		if(priority == priorityMaximum)
			return false;

		setPriority(thread, priority+1);

		Machine.interrupt().restore(intStatus);
		return true;
	}

	public boolean decreasePriority() {
		boolean intStatus = Machine.interrupt().disable();

		KThread thread = KThread.currentThread();

		int priority = getPriority(thread);
		if(priority == priorityMinimum)
			return false;

		setPriority(thread, priority-1);

		Machine.interrupt().restore(intStatus);
		return true;
	}


	/**
	 * The default priority for a new thread. Do not change this value.
	 */
	public static final int priorityDefault = 1;
	/**
	 * The minimum priority that a thread can have. Do not change this value.
	 */
	public static final int priorityMinimum = 0;
	/**
	 * The maximum priority that a thread can have. Do not change this value.
	 */
	public static final int priorityMaximum = Integer.MAX_VALUE;

	protected ThreadState getThreadState(KThread thread) {
		if(thread.schedulingState == null)
			thread.schedulingState = new ThreadState(thread);

		return (ThreadState) thread.schedulingState;
	}

	protected class PriorityThreadQueue extends ThreadQueue{
		PriorityThreadQueue(boolean transferPriority) {
			this.transferPriority = transferPriority;
			this.holder = null;
		}

		public void waitForAccess(KThread thread) {
			Lib.assertTrue(Machine.interrupt().disabled());
			//waitQueue.add(getThreadState(thread));
			getThreadState(thread).waitForAccess(this);
		}
		
		/*
		public void removeResource()
		{
			Lib.debug(dbgPeter, "[+][Priority][removeResource()]");
			if(parent != null && this.transferPriority == true)
				parent.devices.remove(this);
		}
		*/

		public void acquire(KThread thread) {
			Lib.assertTrue(Machine.interrupt().disabled());
			//removeResource();
			getThreadState(thread).acquire(this);
		}
		
		/**We need this function to remove the highest priority thread from the wait queue.
		 * once it is removed calculate its effective priority(which can depend on multiple waitqueues
		 * @return HighestPriority KThread
		 */
		public KThread nextThread(){
			int ticketTotal = 0;
			LinkedList<ThreadState> threads = new LinkedList<ThreadState>();
			LinkedList<Integer> tickets = new LinkedList<Integer>();
			ThreadState nextThread = null;
			int ticketRandom = (int)(Math.random()*ticketTotal);
			int ticketConsumed = 0;

			for(int i = 0; i < waitQueue.size(); i++)
			{
				ThreadState tmp = waitQueue.get(i);
				ticketTotal += tmp.getEffectivePriority();
				threads.add(tmp);
				tickets.add(tmp.getEffectivePriority());
			}

			for(int i = 0; (i < tickets.size()) && ticketTotal > 0; i++)
			{
				ticketConsumed += tickets.get(i);
				
				if((ticketRandom-ticketConsumed) < 0)
				{
					nextThread = threads.get(i);
					break;
				}
			}

			if(transferPriority && nextThread != null)
			{
				if(this.holder != null)
					this.holder.removeQueue(this);
				nextThread.waiting = null;
				nextThread.addQueue(this);
			}
			this.holder = nextThread;
			
			if(this.holder != null)
			{
				this.waitQueue.remove(holder);
				this.holder.setEffectivePriority();
				return this.holder.thread;
			}

			return null;
		}

		/**
		 * Return the next thread that <tt>nextThread()</tt> would return,
		 * without modifying the state of this queue.
		 *
		 * @return the next thread that <tt>nextThread()</tt> would
		 * return.
		 */
		protected ThreadState pickNextThread() {
			boolean intStatus = Machine.interrupt().disable();

			Machine.interrupt().restore(intStatus);

			int ret=0;
			int pos=0;
			for(int i=0; i < waitQueue.size(); i++)
			{
				int tmp = waitQueue.get(i).getEffectivePriority();
				if(tmp > ret)
				{
					ret = tmp;
					pos = i;
				}
			}
			
			return waitQueue.remove(pos);
		}
		
		public void print() {
			Lib.assertTrue(Machine.interrupt().disabled());
			// implement me (if you want)
		}
		
		public void addQueue(ThreadState threadState) {
			this.waitQueue.add(threadState);
		}

		public void removeQueue(ThreadState threadState) {
			this.waitQueue.remove(threadState);
		}

		
		/**
		 * <tt>true</tt> if this queue should transfer priority from waiting
		 * threads to the owning thread.
		 */
		public boolean transferPriority;
		
		protected LinkedList<ThreadState> waitQueue = new LinkedList<ThreadState>();
		public ThreadState holder;
	}
	
	/**
	 * The scheduling state of a thread. This should include the thread's
	 * priority, its effective priority, any objects it owns, and the queue it's
	 * waiting for, if any.
	 * 
	 * @see nachos.threads.KThread#schedulingState
	 */
	protected class ThreadState {
		/**
		 * Allocate a new <tt>ThreadState</tt> object and associate it with the
		 * specified thread.
		 * 
		 * @param thread the thread this state belongs to.
		 */
		public ThreadState(KThread thread) {
			this.thread = thread;

			this.acquired = new LinkedList<PriorityThreadQueue>();
			this.priority = priorityDefault; 
		}

		/**
		 * Return the priority of the associated thread.
		 *
		 * @return the priority of the associated thread.
		 */
		public int getPriority() {
			return priority;
		}

		// dirty bit for the performance? Nah...
		public void setEffectivePriority() {
			int effective = this.getEffectivePriority();
			int originalPriority = this.getPriority();
			int adjustment = 0;

			if(acquired.isEmpty() == false)
				for(int i = 0; i < acquired.size(); i++)
				{
					for(int j=0; j < acquired.get(i).waitQueue.size(); j++)
					{
						ThreadState tmp = acquired.get(i).waitQueue.get(j);
						adjustment += tmp.getEffectivePriority();
					}
				}

			this.effPriority = originalPriority + adjustment;

			if(this.waiting != null && this.waiting.holder != null)
				this.waiting.holder.addTickets(this.effPriority - effective);
		}

		public int getEffectivePriority() {
			return this.effPriority;
		}

		/**
		 * Set the priority of the associated thread to the specified value.
		 *
		 * @param priority the new priority.
		 */
		public void setPriority(int priority) {
			this.priority = priority;
			this.setEffectivePriority();
		}

		// adds tickets to children recursively
		public void addTickets(int ticketNum){
			this.effPriority += ticketNum;
			
			if(this.waiting != null && this.waiting.holder != null) {
				this.waiting.holder.addTickets(ticketNum);
			}
		}

		/**
		 * Called when <tt>waitForAccess(thread)</tt> (where <tt>thread</tt> is
		 * the associated thread) is invoked on the specified priority queue.
		 * The associated thread is therefore waiting for access to the resource
		 * guarded by <tt>waitQueue</tt>. This method is only called if the
		 * associated thread cannot immediately obtain access.
		 * 
		 * @param waitQueue the queue that the associated thread is now waiting
		 * on.
		 * 
		 * @see nachos.threads.ThreadQueue#waitForAccess
		 */
		public void waitForAccess(PriorityThreadQueue waitQueue) {
			Lib.assertTrue(Machine.interrupt().disabled());

			waitQueue.addQueue(this);
			if(waitQueue.transferPriority) {
				this.waiting = waitQueue;
			}
			this.setEffectivePriority();
			if(waitQueue.holder != null) {
				waitQueue.holder.setEffectivePriority();
			}
		}

		/**
		 * Called when the associated thread has acquired access to whatever is
		 * guarded by <tt>waitQueue</tt>. This can occur either as a result of
		 * <tt>acquire(thread)</tt> being invoked on <tt>waitQueue</tt> (where
		 * <tt>thread</tt> is the associated thread), or as a result of
		 * <tt>nextThread()</tt> being invoked on <tt>waitQueue</tt>.
		 *
		 * @see nachos.threads.ThreadQueue#acquire
		 * @see nachos.threads.ThreadQueue#nextThread
		 */
		public void acquire(PriorityThreadQueue waitQueue) {
			Lib.assertTrue(Machine.interrupt().disabled());
			Lib.assertTrue(waitQueue.waitQueue.isEmpty());
			waitQueue.holder = this;
			if(waitQueue.transferPriority) {
				this.addQueue(waitQueue);
			}
			this.setEffectivePriority();
		}

		public void removeQueue(PriorityThreadQueue queue) {
			acquired.remove(queue);
			this.setEffectivePriority();
		}
		
		public void addQueue(PriorityThreadQueue queue) {
			acquired.add(queue);
			this.setEffectivePriority();
		}

		protected KThread thread;

		protected int effPriority;
		protected PriorityThreadQueue waiting = null;
		// linked list of all acquired resources
		protected LinkedList<PriorityThreadQueue> acquired = null;
		
		/** The priority of the associated thread. */
		protected int priority;
	}
	
	private static final char dbgPeter = 'P';
}